public class code02 {
//    力扣 150 二叉树的最近公共祖先
// 创建出一个全局变量的节点，用来记录递归中找到的父节点
TreeNode re = null;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 创建出一个方法用来进行递归运算
        getOther(root, p, q);
        return re;
    }

    public boolean getOther(TreeNode root, TreeNode p , TreeNode q) {
        // 使用后序遍历，先找到二叉树的最底层节点
        // 之后从下向上根据要求进行递归
        if(root == null) {
            return false;
        }

        // 通过中序遍历向深层进行遍历
        // 这两个参数记录的是当前节点是否包含着 p， q
        // 这里的两个参数就像是标记位，从下向上返回递归时，从出现当前节点开始，记录下这条路劲中就包含着 p 或者 q 节点
        // 也就记录下这条路径中剩余的节点都为 true
        boolean leftTree = getOther(root.left, p, q);
        boolean rightTree = getOther(root.right, p, q);

        // 这里要做到的就是找到最小公共子树
        // 这里要判断的是
        // 当左右节点都为 true 时，其上面对应的父节点就是公共节点
        // 就是当当前值为 p 或 q 时，并且在这条路径中包含 true。此时就说明这个 p 或者 q 本身它就是一个父节点
        if((leftTree && rightTree) || ((root.val == p.val || root.val == q.val) && (leftTree || rightTree))) {
            re = root;
        }

        // 这里可以先来确定返回值
        // 这里就是用来确定只要在左右子树中出现了 p 或者 q 就返回 true
        // 也就是说可以在这两个子树的结合处找到最小公共子树
        return leftTree || rightTree || (root.val == p.val || root.val == q.val);
    }
}
